#include <cstddef>
#include <iostream>
#include <assert.h>
#include <iterator>
#include <list>
#include <utility>

using std::cout;
using std::endl;

namespace real{

    template <class T>
    class ListNode{
        public:
            T _data;
            ListNode* _next;
            ListNode* _prev;

            ListNode(const T& data = T())
                :_data(data)
                ,_next(nullptr)
                ,_prev(nullptr)
            {}
    };

    template<class T_DATA, class Ref, class Ptr >
    struct list_iterator
    {
        /*
        typedef list_iterator<T_DATA> iterator;
        typedef list_const_iterator<T_DATA> const_iterator;
        */
        typedef ListNode<T_DATA> Node;
        typedef list_iterator<T_DATA, Ref, Ptr> Self;
        Node* _pnode;

        list_iterator(Node* pnode)
            :_pnode(pnode)
        {}

        Ref operator*()
        {
            return _pnode->_data;
        }

        // T_DATA* operator->()
        Ptr operator->()
        {
            return &(_pnode->_data);
        }

        Self& operator++()
        {
            _pnode = _pnode->_next;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp = *this;
            _pnode = _pnode->_next;
            return tmp;
        }

        Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

        Self operator--(int)
		{
            Self tmp = *this;
            _pnode = _pnode->_prev;
            return tmp;
        }

        bool operator!=(const Self& other) const
        {
            return _pnode != other._pnode;
        }

        bool operator==(const Self& other) const
        {
            return _pnode == other._pnode;
        }

        // Self operator->()
        // {
        //     return _pnode;
        // }
    };

    template <class T>
    class list
    {
    private:
        typedef ListNode<T> Node;
        Node* _head = nullptr;
        size_t _size = 0;

    public:
        typedef list_iterator<T, T&, T*> iterator;
        typedef list_iterator<T, const T&, const T*> const_iterator;
        void initList()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0 ;
        }

        // default constructor
        list()
        {
            initList();
        }

        // fill
        list(size_t n, const T& val=T())
        {
            initList();
            for(size_t i = 0; i < n; i++)
            {
                push_back(val);
            }
        }
        
        // copy constructor
        list(const list<T>& other)
        {   
            cout << "copy constructor" << endl;
            initList();
            // for(Node* it = other._head->_next; it != other._head; it = it->_next)
            // {
            //     push_back(it->_data);
            // }

            const_iterator it = other.cbegin();
            while(it != other.cend() )
            {
                push_back(it._pnode->_data);
                ++it;
            }
        }

        void push_back(const T& val)
        {
            // Node* newnode = new Node(val);
            // Node* last = _head->_prev;
            // last->_next = newnode;
            // _head->_prev = newnode;
            // newnode->_prev = last;
            // newnode->_next = _head;
            // _size++;
            insert(_head, val);
        }

        void push_front(const T& val)
        {
            insert(_head->_next, val);
        }

        void insert(iterator pos, const T& val)
        {
            Node* newnode = new Node(val);
            Node* prev = pos._pnode->_prev;
            newnode->_prev = prev;
            newnode->_next = pos._pnode;
            prev->_next = newnode;
            pos._pnode->_prev = newnode;
            _size++;
        }

        // 返回迭代器 解决迭代器失效的问题
        iterator erase(iterator pos)
        {
            assert(!empty());
            Node* next = pos._pnode->_next;
            next->_prev = pos._pnode->_prev;
            pos._pnode->_prev->_next = next;
            delete pos._pnode;
            _size--;
            return next;
        }

        iterator pop_front()
        {
            return erase(begin());
        }

        iterator pop_back()
        {
            return erase(--end());
        }

        iterator begin()
        {
            return _head->_next;
        }

        const_iterator cbegin() const
        {
            return _head->_next;
        }

        iterator end()
        {
            return _head;
        }

        const_iterator cend() const
        {
            return _head;
        }

        size_t size()
        {
            return _size;
        }

        bool empty()
        {
            return _size == 0;
        }

        void clear()
        {
            // assert(!empty());
            auto iter = begin();
            while(iter!=end())
            {
                iter = pop_back();
                // iter++; //++多跳过了一个单位
            }
        }

        void swap(list& other)
        {
            std::swap(_head, other._head);
            std::swap(_size, other._size);
        }

        list& operator=(list other)
        {
            swap(other);
            return *this;
        }

        ~list()
        {
            cout << "~list()" <<endl;
            clear();
            delete _head;
            _head = nullptr;
            _size = 0 ;
        }
    };

    template <class T>
    void print_iterator(T& t)
    {
        for(auto e: t)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}